package practice_7_23;

class Solution {
    /**
     * 最长递增子序列
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        // dp[i]: 以 i 为结尾的最长递增子序列
        // dp[i]: i 位置之前的元素, 加上 i 后, 能构成的最长递增子序列
        int n = nums.length;
        int[] dp = new int[n];
        int max = 1;
        for(int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    /**
     * 摆动序列
     * @param nums
     * @return
     */
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        // f[i]: 以 n 为结尾的最长摆动序列, 此时摆动为正数
        // g[i]: 以 n 为结尾的最长摆动序列, 此时摆动为负数
        int[] f = new int[n];
        int[] g = new int[n];
        for(int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
        }
        // int max = 1;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    f[i] = Math.max(f[i], g[j] + 1);
                } else if (nums[i] < nums[j]) {
                    g[i] = Math.max(g[i], f[j] + 1);
                }
            }
        }
        return Math.max(g[n - 1], f[n - 1]);
    }
}